package com.killer.linear;

/**
 * 数组队列
 */
public class MyArrayQueue<T> implements MyQueue<T> {

    /**
     * 底层存储数组
     */
    private Object[] arrs;

    /**
     * 元素个数
     */
    private int size=0;

    /**
     * 头指针
     */
    private int head=0;

    /**
     * 尾指针(尾指针所在的下标并没有数据,最后一个数据在tail-1处)
     */
    private int tail=0;

    public MyArrayQueue(){
        //容量默认为4
        this.arrs = new Object[4];
    }

    public void offer(T t) {
        //判断是否需要扩容
        if (size >= arrs.length - 1) {
            //由于要区分空队列还是满队列,当头尾指针在一起时定义为空队列,满队列是头指针比尾指针大1,
            // 因此length长度数组只能方length-1个元素
            resize();
        }
        size++;
        //这里要判断,如果tail在0处,证明上一个元素在数组尾部
        arrs[tail]=t;
        //判断尾指针是否已经到末尾
        if (tail == arrs.length - 1) {
            //已到末尾就循环走一遍回到0
            tail=0;
        }else{
            tail++;
        }
    }

    private void resize() {
        //创建一个新数组,容量是原来的2倍
        Object[] newArr = new Object[arrs.length * 2];
        //数组赋值(要分两种情况)
        if (tail > head) {
            //如果尾指针大于头指针,则只要包头指针和尾指针之间的数据拷贝到新数组即可
            for(int i=head;i<tail;i++) {
                newArr[i - head] = arrs[i];
            }
        }else{
            //头指针大于了尾指针,证明头指针到末尾有元素,然后数组头部到尾指针之间也有元素
            for(int i=head;i<arrs.length;i++) {
                newArr[i - head] = arrs[i];
            }
            for(int i=0;i<tail;i++) {
                newArr[i+head]=arrs[i];
            }
        }

        arrs=newArr;
        //重设首尾指针
        head=0;
        tail=size;
    }

    public T poll() {
        //判断是否已经是空队列
        if (head == tail) {
            throw new RuntimeException("队列已经为空");
        }
        size--;
        //头指针往前移动
        return (T)arrs[head++];
    }

    public int size() {
        return size;
    }
}
